package com.example.suanfa;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {421, 240, 115, 532, 305, 430, 124};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }

    static int[] sort(int[] arr) {
        //result用来存储结果
        int[] result = new int[arr.length];
        //
        int[] count = new int[10];
        //i<小于数组的最大位数
        for (int i = 0; i < 3; i++) {
            //抬高位数
            int divistion = (int) Math.pow(10, i);
            System.out.println(divistion);
            for (int j = 0; j < arr.length; j++) {
                //取相应的位数
                int num = arr[j] / divistion % 10;
                System.out.print(num + " ");
                count[num]++;
            }
            System.out.println();
            System.out.println(Arrays.toString(count));
            //累加数组，保持相对位置
            for (int m = 1; m < count.length; m++) {
                count[m] = count[m] + count[m - 1];
            }
            System.out.println(Arrays.toString(count));
            //按照所选位数的顺序将数字放回结果集
            for (int n = arr.length - 1; n > 0; n--) {
                int num = arr[n] / divistion % 10;
                result[--count[num]] = arr[n];
            }
            System.out.println(Arrays.toString(result));
            System.arraycopy(result, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);
        }
        return result;
    }
}
